%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}
\usepackage{pgfplots}
%\pgfplotsset{width=10cm,compat=1.9}
%\usepgfplotslibrary{external}
%
%\tikzexternalize
%



\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}

\usepackage[variablett]{lmodern}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
%  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  language=C++,
%  basicstyle=\ttfamily,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
%  gobble=4,
%  xleftmargin=\leftmargini, 
%  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{green},      % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  extendedchars=true,              
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 
  keywordstyle=\color{blue},       % keyword style
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{black}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showstringspaces=false,          % underline spaces within strings only
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mauve},    	% string literal style
%  tabsize=4,                       % sets default tabsize to 2 spaces 
  title=\lstname,                   % show the filename of files included with \lstinputlisting; also try caption instead of title
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title[Short title]{Expérimentation sur GAC, MaxRPWC1, MaxRPWC3, rPIC, RPWC} % The short title appears at the bottom of every slide, the full title is only on the title page
\vspace{0.2cm}
\vspace{0.2cm}
\author{
Etudiant: KHONG Minh Thanh\\
Superviseurs: Yves Deville, Jean-Baptiste Mairy
\vspace{0.4cm}
}

\institute{
Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%----------------------------------------------------------------------------------------
%	PRESENTATION SLIDES
%----------------------------------------------------------------------------------------
%
%%------------------------------------------------
%\section{MaxRPWC1} 
%%------------------------------------------------
%\begin{frame}[fragile]
%\frametitle{Max-RPWC-1}
%Algorithme MaxRPWC1 \cite{domain:2008} 
%\begin{lstlisting}[caption=function Revise of Max-RPWC-1]
%function Revise($x_j, c_i,MaxRPWC$)
%   for each value $a \in D(x_j)$
%      PW $\leftarrow$ FALSE;
%      foreach valid $\tau (\in rel(c_i)) \geq_l lastGAC_{x_j,a,c_i}$ s.t. $\tau[x_j] = a$
%         PW $\leftarrow$ TRUE;
%         for each $c_m \neq c_i$ s.t. $|vars(c_i) \cap vars(c_m)| > 1$
%            if $\nexists$ valid $\tau' (\in rel(c_m))$ s.t. $\tau[vars(c_i) \cap vars(c_m)] = \tau' [vars(c_i) \cap vars(c_m)]$
%               PW $\leftarrow$ FALSE; break;
%         if PW = TRUE $lastGAC_{x_j,a,c_i} \leftarrow \tau$; break;
%      if PW = FALSE remove $a$ from $D(x_j)$;
%   return number of deleted values;
%\end{lstlisting}
%{\footnotesize
%Ligne 4-10 : pour chaque valide tuple $\tau \in rel(c_m), \tau[x_j]=a$, tester s'il peut étendre aux autres contraintes intersectées avec $c_i$. Si non, enlever $a$ de $D(x_j)$.\\
%Ligne 6-7 : pour chaque contrainte $c_m$, tester si $\tau$ a PW-support $\tau'$ dans $c_m$.\\
%Complexité : time : $O(e^2k^2d^p)$, space : $O(ekd)$, p : maximum nombre de variables dans deux contraintes intersectées
%
%}
%\end{frame}

%------------------------------------------------

%%------------------------------------------------
%\section{MaxRPWC}
%%------------------------------------------------
%%------------------------------------------------
%\section{Implémentation}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Implémentation}
%Il y a deux classes principale à faire :
%\begin{itemize}
%\item MaxRPWC3 : 
%	\begin{itemize}
%	\item appeler la propagation 
%	\item trouver les intersections entre les contraintes
%	\end{itemize}
%\item ConstraintHardExtensionRPWC3 :
%	\begin{itemize}
%	\item contenir la méthode "runPropagator(Variable)" qui fait la fonction "Revise($x_j, c_i,MaxRPWC$)" pour réviser la consistance des variables de la contrainte
%	\end{itemize}
%\end{itemize}
%\end{frame}
%
%%------------------------------------------------
%
%\begin{frame}[fragile]
%\frametitle{Implémentation}
%Implémentation de la méthode "runPropagator(Variable)" :
%\begin{lstlisting}[caption=function runPropagator(Variable)]
%ConstraintHardExtensionRPWC3.runPropagator(Variable)
%   // $c_i$ is this constraint
%   for each variable $x_j \in c_i$ 
%      Revise($x_j, c_i,MaxRPWC$)
%   // update domain of all variable in $c_i$, return false if a domain of variable is empty   
%   return updateDomain()
%\end{lstlisting}
%\begin{itemize}
%\item Problème : 
%Ne pas implémenter $lastGAC_{x_j,a,c_i}$ à cause du changement des indexes des tuples, on doit donc chaque fois parcourir au début des tuples.
%\item Modification : 
%Enlever les tuples qui ne peut pas étendre aux autres tuples dans la fonction "Revise($x_j, c_i,MaxRPWC$)", il diminue les tuples à parcourir chaque fois
%\end{itemize}
%\end{frame}

%------------------------------------------------
\section{Expérimentation}
%------------------------------------------------
\begin{frame}
\frametitle{Expérimentation}
\begin{itemize}
\item L'expérimentation est lancé sur un PC de 4GB RAM, Core i5-2520M, Ubuntu. 
\item Le problèmes utilisés sont renault, random, random-fcd dans \cite{problem}. Le nombre de variable intersecté est 2-10.
\item Les consistances à tester sont GAC(algo STR2), MaxRPWC1, MaxRPWC3, rPIC, RPWC, PWC.
\item Les critères à considérer sont CPU time(s), et node.
\end{itemize}
\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
\small{
Le résultat (CPU time(s), node) :}
\begin{center}
\scalebox{0.75}{
    \begin{tabular}{ | l | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
    \hline
    Problème  & GAC        & RPWC 		& rPIC 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    renault-0 & 0.72, 166  & 4.336, 114 	& 21.60, 111 & 51.17, 111 & 65.25, 111 & 3.29, 111\\ \hline
    renault-1 & 2.91, 53775  & 285.73, 43244& 118, 818 & 32.44, 0 & 20.66, 0 & 1.72, 0\\ \hline
    renault-2 & 0.77, 111  & 1.65, 111& 31.17, 111 & 37.07, 111 & 47.49, 111 & 2.03, 111 \\ \hline
    renault-3 & 1390.86, 20994648 & 17872.2, 16992656 & $>$36000, - & 30.00, 0 & 45.80, 0& 1.52, 0\\ \hline
    renault-4 & 0.67, 114 & 1.64, 112 & 22.93, 112 & 34.55, 112 & 30.60, 112 & 2.17, 112\\ \hline
    renault-5 & 213.82, 3231085 & 409.95, 44491& 647.82, 12825 &  102.09, 241 & 98.84, 241 & 1.57, 0\\ \hline
    renault-6 & 4.64, 115411 & 289.72, 59526 & 985.77, 59507 & 522.77, 52831 & 569.82, 52831 & 6.45, 52831\\ \hline
    renault-7 &  0.7, 134 & 3.50, 120& 28.33, 113&  42.17, 113 & 43.26, 113 & 2.06, 112\\ \hline
    renault-8 & 5.67, 180955 & 608.05, 111363 & 1745.68, 86045 & 456.98, 12336 & 257.66, 12336 & 2.24, 0\\ \hline
    renault-9 & 0.68, 254 & 2.70, 148& 30.75, 113 &  59.53, 113 & 32.84, 113& 1.86, 111\\ \hline
    \end{tabular}
}
\end{center}
\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Expérimentation}
\small{
Le résultat (CPU time(s), node) :}
\begin{center}
\scalebox{0.75}{
    \begin{tabular}{ | p{2.0cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} | p{1.3cm} |}
    \hline
    Problème  & GAC        & RPWC 		& rPIC 		& Max-RPWC1 	& Max-RPWC3 	& PWC+ GAC	\\ \hline
    rand-3-20-20-60-632-4\_ext & \textbf{12.02, 31453} & 689.7, 76152 & 889.6, 66270 & 767.4, 66270 & 372.3, 66270 & 188.9, 147687 \\ \hline
    rand-3-20-20-60-632-8\_ext & \textbf{16.57}, 43795  & 424.2, 62650 & 661.6, 58323 & 542.78, 58323 & 287.6, 58323 & 38.1, \textbf{20825}\\ \hline
    rand-3-20-20-60-632-9\_ext & \textbf{39.62}, 71345 & 242.7, \textbf{24975} & 1045.7, 77462 & 947.5, 77462 & 478.7, 77462 & 106.7, 47391\\ \hline
    rand-3-20-20-60-632-fcd-15\_ext & \textbf{29.26}, 43555 & 349.12, 48113 & 449.5, 37727 & 394.83, 37727 & 200.4, 37727 & 42.3, \textbf{16545}\\ \hline
    rand-3-20-20-60-632-fcd-2\_ext & 39.49, 49866 & 276.3, 36338 & 619.0, 43740 & 522.0, 43740 & 266.8, 43740 & \textbf{9.45, 3636} \\ \hline
    rand-3-20-20-60-632-fcd-8\_ext & \textbf{38.30}, 83173 & 333.5, \textbf{54973} & 1420.4, 105426 & 982.4, 105426& 501.4, 105426 & 122.0, 95600\\ \hline
    \end{tabular}
}
\end{center}
\end{frame}

%%------------------------------------------------
%%
%\begin{frame}
%\frametitle{Expérimentation}
%
%\begin{tikzpicture} 
%\begin{loglogaxis}[ xlabel={renault instance}, ylabel={Temps d'exécution(s)} ] 
%\addplot coordinates { (5,8.312e-02) (17,2.547e-02) (49,7.407e-03) (129,2.102e-03) (321,5.874e-04) (769,1.623e-04) (1793,4.442e-05) (4097,1.207e-05) (9217,3.261e-06) }; 
%\addplot coordinates{ (7,8.472e-02) (31,3.044e-02) (111,1.022e-02) (351,3.303e-03) (1023,1.039e-03) (2815,3.196e-04) (7423,9.658e-05) (18943,2.873e-05) (47103,8.437e-06) }; 
%\addplot coordinates{ (9,7.881e-02) (49,3.243e-02) (209,1.232e-02) (769,4.454e-03) (2561,1.551e-03) (7937,5.236e-04) (23297,1.723e-04) (65537,5.545e-05) (178177,1.751e-05) }; 
%\addplot coordinates{ (11,6.887e-02) (71,3.177e-02) (351,1.341e-02) (1471,5.334e-03) (5503,2.027e-03) (18943,7.415e-04) (61183,2.628e-04) (187903,9.063e-05) (553983,3.053e-05) }; 
%\addplot coordinates{ (13,5.755e-02) (97,2.925e-02) (545,1.351e-02) (2561,5.842e-03) (10625,2.397e-03) (40193,9.414e-04) (141569,3.564e-04) (471041,1.308e-04) (1496065,4.670e-05) }; 
%\legend{$GAC$,$MaxRPWC1$,$MaxRPWC3$,$rPIC$,$RPWC$} 
%\end{loglogaxis} 
%\end{tikzpicture}
%\end{frame}

%------------------------------------------------
%
%\begin{frame}
%\frametitle{Expérimentation}
%
%\end{frame}
%
%%------------------------------------------------
%
%%------------------------------------------------
%\section{Perspective}
%%------------------------------------------------
%\begin{frame}
%\frametitle{Perspective}
%
%\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
\bibitem{domain:2008} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
\bibitem{problem} http://www.cril.univ-artois.fr/lecoutre/benchmarks.html
\end{thebibliography}
}
\end{frame}

%%------------------------------------------------
%
%\begin{frame}
%\Huge{\centerline{The End}}
%\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 